package com.yww.datastructure.line.array;

import com.yww.datastructure.line.Linear;

import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.Stream;

/**
 * @author yww
 * @description 动态数组
 * @since 2024/1/29 17:15
 */
public final class DynamicArray<E> implements Linear<E> {
    /**
     * size 指向最后待插入索引
     **/
    private int size;
    private int capacity = 10;
    private Object[] elements;

    public DynamicArray() {
    }

    public DynamicArray(int capacity) {
        this.capacity = capacity;
    }

    @Override
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("非法index：" + index);
        }
        return (E) elements[index];
    }

    public void addLast(E e) {
        add(e, size);
    }

    @Override
    public void addFirst(E e) {
        add(e, 0);
    }

    public void add(E e, int index) {
        // 扩容
        checkAndGrow();
        // 如果不是往末尾添加，index及后面的元素往后移动
        if (index >= 0 && index < size) {
            System.arraycopy(elements, index, elements, index + 1, size - index);
        }

        // index 插入新元素
        elements[index] = e;
        size++;
    }

    /**
     * 删除索引index的元素，并返回
     *
     * @param index
     * @return E
     **/
    public E remove(int index) {
        E removed = (E) elements[index];
        if (index < size - 1) {
            // 后面的元素往前移
            System.arraycopy(elements, index + 1, elements, index, size - index - 1);
        }
        size--;
        return removed;
    }

    @Override
    public E removeLast() {
        return remove(size - 1);
    }

    @Override
    public E removeFirst() {
        return remove(0);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 检查并扩容
     **/
    private void checkAndGrow() {
        if (elements == null || elements.length == 0 || capacity < 10) { // 是否被初始化
            capacity = 10;
            elements = new Object[capacity];
        } else if (size == capacity) { // 最后一个待插入位置已经越界，进行1.5倍扩容
            capacity += capacity >> 1;
            Object[] newElements = new Object[capacity];
            System.arraycopy(elements, 0, newElements, 0, size);
            elements = newElements;
        }
    }

    public void foreach(Consumer<E> consumer) {
        for (int i = 0; i < size; i++) {
            consumer.accept((E) elements[i]);
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int i = 0;

            @Override
            public boolean hasNext() { // 是否还有下一个元素
                return i < size;
            }

            @Override
            public E next() {
                return (E) elements[i++];
            }
        };
    }

    public Stream<E> stream() {
        return (Stream<E>) Stream.of(Arrays.copyOfRange(elements, 0, size));
    }
}
